// https://www.lintcode.com/problem/minimum-moves/

public class Solution {
    /**
     * @param S: a string
     * @return:  return the minimum number of moves
     */
    public int MinimumMoves(String S) {
        // write your code here
        int ret = 0;
        if (S.length() > 0) {
            StringBuilder sb = new StringBuilder();
            sb.append(S);
            sb.append(' '); // 因为最后一个字符也要判断，所以额外加个空格。
            S = sb.toString();
            int n = 1;
            Character c = S.charAt(0);
            for (int i = 1; i < S.length(); ++i) {
                if (c == S.charAt(i)) {
                    ++n;
                } else {
                    ret += (n / 3); // 根据之前连续的数目决定要移动几次
                    c = S.charAt(i);
                    n = 1;
                }
            }
        }
        return ret;
    }
}